package indi.imooc.algorithm.insertionsort;

import indi.imooc.algorithm.sortInterface.SortInterface;
import indi.utils.ArrayGeneratorUtil;
import indi.utils.SortingHelper;

import java.util.Arrays;

/**
 * 插入排序算法
 * arr[0,i)已排序,arr[i,n)未排序
 * 对于插入排序,如果数组是有序的,时间复杂度是O(n);二选择排序的时间复杂度永远是O(n^2)
 * 适用场景,大部分数据为有序数组时,例如,银行数据一般是按照时间排序,某些数据开始时间较早,但是处理时间较长,导致这部分数据不是有序排列
 */
public class InsertionSort implements SortInterface {

//    @Override
//    public <E extends Comparable<E>> void sort(E[] arr) {
//        for (int i = 0; i < arr.length; i++) {
//            int j = i ;
//            while (j > 0){
//                if(arr[j].compareTo(arr[j - 1]) >= 0){
//                }else {
//                    swap(arr,j - 1,j);
//                }
//                j--;
//            }
//        }
//    }


//    @Override
//    public <E extends Comparable<E>> void sort(E[] arr) {
//        for (int i = 0; i < arr.length; i++) {
//            for (int j = i; j > 0 && arr[j].compareTo(arr[j - 1]) < 0 ; j--) {
//                swap(arr,j - 1,j);
//            }
//        }
//    }

    @Override
    public <E extends Comparable<E>> void sort(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if(arr[j].compareTo(arr[j - 1]) < 0){
                    swap(arr,j - 1,j);
                }else {
                    break;
                }
            }
        }

    }

    private <E>  void swap(E[] arr,int i,int j){
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 优化版本
     * @param arr
     * @param <E>
     */
//    @Override
//    public <E extends Comparable<E>> void sort2(E[] arr) {
//        for (int i = 0; i < arr.length; i++) {
//            E temp = arr[i];
//            for (int j = i; j > 0; j--) {
//                if (arr[j - 1].compareTo(temp) > 0){
//                    arr[j] = arr[j - 1];
//                }else{
//                    arr[j] = temp;
//                }
//            }
//        }
//    }

    /**
     * 官方版本
     * sort每次交换涉及到数组的三次赋值操作,优化后只会赋值一次
     * @param arr
     * @param <E>
     */
    @Override
    public <E extends Comparable<E>> void sort2(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            E temp = arr[i];
            int j;
            for (j = i; j > 0 && arr[j - 1].compareTo(temp) > 0; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
    }

    /**
     * 从末尾开始排序
     * arr[0,i)已排序,arr[i,n)未排序
     * @param arr
     * @param <E>
     */
    @Override
    public <E extends Comparable<E>> void sort3(E[] arr) {
        for (int i = arr.length - 1; i >= 0 ; i--) {
            E temp = arr[i];
            int j;
            for (j = i; j <  arr.length - 1 && arr[j + 1].compareTo(temp) < 0; j++) {
                arr[j] = arr[j + 1];
            }
            arr[j] = temp;
        }
    }

    public static void main(String[] args) {
        Integer[] data = {1000,10_000};
//        Integer[] data = {10};
        for(int n : data){
            System.out.println("random array");
            Integer[] arr = ArrayGeneratorUtil.generateRandomArray(n,n);
            Integer[] arr2 = Arrays.copyOf(arr,arr.length);
            SortingHelper.testSort(InsertionSort.class,"insertionSort",arr);
//            SortingHelper.testSort(SelectionSort.class,"selectionSort",arr2);

            System.out.println();
            System.out.println("ordered array");
            arr = ArrayGeneratorUtil.generateOrderedArray(n);
            arr2 = Arrays.copyOf(arr,arr.length);
            SortingHelper.testSort(InsertionSort.class,"insertionSort",arr);
//            SortingHelper.testSort(SelectionSort.class,"selectionSort",arr2);
        }
    }
}
